package goleetcode

func minimumMountainRemovals(nums []int) int {
	n := len(nums)
	pre := getLISArray(nums)
	suf := getLISArray(reversed(nums))
	suf = reversed(suf)

	ans := 0
	for i := 0; i < n; i++ {
		if pre[i] > 1 && suf[i] > 1 {
			ans = max(ans, pre[i] + suf[i] - 1)
		}
	}
	return n - ans
}

func getLISArray(nums []int) []int {
	n := len(nums)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[j] {
				dp[i] = max(dp[i], dp[j] + 1)
			}
		}
	}
	return dp
}

func reversed(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	for i := 0; i < n; i++ {
		ans[i] = nums[n - 1 - i]
	}
	return ans
}